class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def backtrack(start, path):
            nonlocal res
            if len(path) == 4 and start == len(s):
                res.append('.'.join(path))
                return
            if len(path) == 4 or start == len(s):
                return
            for i in range(1, 4):
                if start + i > len(s):
                    break
                if i > 1 and s[start] == '0':
                    break
                num = int(s[start:start + i])
                if num > 255:
                    break
                path.append(str(num))
                backtrack(start + i, path)
                path.pop()

        res = []
        backtrack(0, [])
        return res